package org.nowcoder.leetcode.sort;

import java.util.*;

/**
 * Title  : 147. Insertion Sort List
 * Source : https://leetcode.cn/problems/insertion-sort-list
 * Author : XrazYang
 * Date   : 2023-09-19
 */

public class LeetCode_147 {
    class ListNode {
        public int val;
        public ListNode next;

        public ListNode() {
        }

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode insertionSortList(ListNode head) {
        //朴素解法： 将链表转为数组
        ListNode p = head;
        List<Integer> vals = new ArrayList<>();
        while (p != null) {
            vals.add(p.val);
            p = p.next;
        }

        p = head;
        Collections.sort(vals);
        for (Integer val : vals) {
            p.val = val;
            p = p.next;
        }
        return head;
    }
}
